package leetcode.hard;

import leetcode.base.TreeNode;

/**
 * ClassName: $124_MaxPathSum
 * Description:
 * date: 2021-11-19 23:59
 *
 * @author liyifan
 */
public class $124_MaxPathSum {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return max;
    }

    public int dfs(TreeNode root){
        if (root == null)
            return 0;

        int left = Math.max(dfs(root.left), 0);
        int right = Math.max(dfs(root.right), 0);

        int currentSum = left + right + root.val;
        max = Math.max(max, currentSum);
        return root.val + Math.max(left, right);
    }
}
